package doublePointer;

import java.util.ArrayList;
import java.util.Iterator;

public class moveZeroes {
    // 暴力，记录所有0的位置，然后移动
    // 一开始想着减少操作，只移动两个0位置之间的，但是不行，必须移动全部的
    public static void moveZeroes1(int[] nums) {
        // 不能复制数组,要原地对数组操作
        // 记录0的位置
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                list.add(i);
            }
        }
        // 不包含0
        if (list.size() == 0) {
            // 无需输出
            // for (int n : nums) {
            // System.out.println(n);
            // }
            return;
        }
        // 移动数组
        Iterator<Integer> iterator = list.iterator();
        int offset = 0;
        int lastIndex = 0;
        int firstIndex = 0;
        while (iterator.hasNext()) {
            Integer next = iterator.next();
            // 考虑结尾已经全是0的情况
            // 考虑有连续0的情况 1 2 3 0 0 0 4 5 0 6 7
            int batch = 1;
            while (list.contains(next + 1)) {
                batch++;
                next = iterator.next();
            }
            // 需要偏移，因为之前移动过了
            next -= offset;
            // 找到first和last的index
            firstIndex = next + 1;
            lastIndex = nums.length - offset - 1;

            // 移动
            for (int i = firstIndex; i <= lastIndex; i++) {
                nums[i - batch] = nums[i];
                nums[i] = 0;
            }
            offset += batch;

        }
        

    }

    // 使用双指针
    public static void moveZeroes2(int[] nums) {
        int slow = 0, fast = 0;
        // 1 2 3 4 0 0 1
        while (fast < nums.length) {
            if (nums[fast] != 0) {
                int temp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = temp;
                slow++;
            }
            fast++;
        }
        for (int n : nums) {
            System.out.println(n);
        }
    }

    public static void main(String[] args) {
        // int[] nums = new int[] { 0, 1, 0, 1 };
        int[] nums = new int[] { 0, 1, 0, 3, 12 };
        // int[] nums = new int[] { 0, 0, 1 };
        moveZeroes2(nums);
    }
}
